import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestHeap {
    public int[] elme;
    public int usedSize;
    public TestHeap(){
        this.elme=new int[10];
    }
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elme[i]=array[i];
            usedSize++;
        }
    }
    public void creareHeap(){
        //parent从最后一个元素的父节点开始
        for (int parent = (usedSize-1-1)/2; parent >=0 ; parent--) {
            //parent--,数组下标移动到前一个元素
            //uesdSize-1=i
            //父亲节点移动，从下标最大值往小的移动
            shiftDown(parent,usedSize);
        }
    }
    //调整方法
    //                       父亲下标       每棵树的结束下标
    //从顶向下调整
    private void shiftDown(int parent,int len){
        int child=2*parent+1;
        while (child<len){
            if (child<(len-1)&&elme[child]< elme[child+1]){
                //child最大取len-2的元素，数组最后一个元素下标为len-1,便于child++不会越界
                child++;
            }
            //孩子比父亲大
            if (elme[child]>elme[parent]){//执行完该if语句继续在while循环
                int tmp=elme[child];
                elme[child]=elme[parent];
                elme[parent]=tmp;
                parent=child;//往下移动
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    //向上调整
    public void shiftUp(int child){
        int parent=(child-1)/2;//求得父亲节点
        while (child>0){
            if (elme[child]>elme[parent]){
                int tmp=elme[child];
                elme[child]=elme[parent];
                elme[parent]=tmp;
                child=parent;//孩子往上移动
                parent=(child-1)/2;//父节点往上移动
            }
            else {
                break;
            }
        }
    }
    public void offer(int val){
        if (isFull()){
            //扩容
            elme=Arrays.copyOf(elme,2*elme.length);
        }
        //下标为usedSize,使用完usedSize后++
        elme[usedSize++]=val;//假如加入元素后有11个
        //向上调整
        shiftUp(usedSize-1);//传入10，最后一个孩子下标为10
    }
    public boolean isFull(){
        return usedSize==elme.length;
    }
    public void pop(){
        if (isEmpty()){
            return ;
        }
        //如为最大根堆，最大元素与末尾元素交换
        swap(elme,0,usedSize-1);
        usedSize--;
        //向下调整
        shiftDown(0,usedSize);//最后一个元素已经删除，所以个数-1

    }
    public boolean isEmpty(){
        return usedSize==0;
    }
    public void swap(int[] arr,int i,int j){
        int tmp=elme[i];
        elme[i]=elme[j];
        elme[j]=tmp;
    }
    //找出数组中最小的k个数。以任意顺序返回这k个数均可 top_k问题
    public int[] smallestK(int[] arr, int k) {
        int[] ret=new int[k];
        if (arr==null||k==0){
            return ret;
        }
        //建立小根堆
        Queue<Integer> minHeap=new PriorityQueue<>(arr.length);

        for (int x:arr ) {
            minHeap.offer(x);
        }
        //在已经建成的小根堆上获取前k个最小元素
        for (int i=0;i<k;i++) {
            ret[i]=minHeap.poll();
        }
        return ret;
    }
    //获取前k个最大元素
    /*获取前k个最大元素，先将数组前K个建成小根堆，
    堆顶元素为前k个数组中最小元素，
    将数组后面arr.lenght-k个元素与堆顶元素比较，
    小于堆顶元素不入堆，因为比前k个还小的元素，该元素一定不是前k个最大
    * */
    public static int[] MaxK(int[] arr, int k) {
        int[] ret=new int[k];
        if (arr==null||k==0){
            return ret;
        }
        Queue<Integer> minHeap=new PriorityQueue<>();
        //将数组前k个建小根堆
        for (int i=0;i<k;i++){
            minHeap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            //如果后面arr.length-k个元素大于堆顶元素，先弹出堆顶元素后入堆
            if (arr[i]>minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        //此时的k个堆元素中一定是前k个最大值
        for (int i=0;i<k;i++) {
            ret[i]=minHeap.poll();
        }
        return ret;
    }
    //获取前k个最小
    /*获取前k个最小元素，先将数组前K个建成大根堆，
    堆顶元素为前k个数组中最大元素，
    将数组后面arr.length-k个元素与堆顶元素比较，
    大于堆顶元素不入堆，因为比前k个还大的元素，该元素一定不是前k个最小元素
    * */
    public int[] smallestK2(int[] arr, int k) {
        int[] ret=new int[k];
        if (arr==null||k==0){
            return ret;
        }
        Queue<Integer> minHeap=new PriorityQueue<>();
        //将数组前k个建大根堆
        for (int i=0;i<k;i++){
            minHeap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            //如果后面arr.length-k个元素小于堆顶元素，先弹后入堆
            if (arr[i]<minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        //此时的k个堆元素中一定是前k个最大值
        for (int i=0;i<k;i++) {
            ret[i]=minHeap.poll();
        }
        return ret;
    }

    public static void main1(String[] args) {
        int[] arr={1,22,33,44,55,66,77,88,99,100};
        int[] ret=MaxK(arr,3);
        System.out.println(Arrays.toString(ret));
    }
    //堆排序
    /*让一组数组从小到大排序
    * 1.按大根堆排序
    * 2.堆顶元素与最后一个元素交换，最后一个元素排除堆
    * 3.堆顶元素向下调整
    * 4.重复交换2，3步*/
    public void HeapSort(){
        int end=usedSize-1;
        while (end>0){
            swap(elme,0,end);
            shiftDown(0,end);//向下调整，父层和子层之间相互比较
            end--;
        }
    }
}
